#ifndef BELLMAN-FORD_H_INCLUDED
#define BELLMAN-FORD_H_INCLUDED
#include "CGraph.h"

template <typename GraphType>
class CFordBellman
{
public:

    CFordBellman(GraphType& graph, const typename GraphType::CVertexIterator& firstVertex);
    ~CFordBellman() {};

    void Process();

    bool HasNegativeCycle() const {return result;}
    const map<typename GraphType::CVertexIterator, typename GraphType::EdgeType>& GetMinPathWeights() const;
    const map<typename GraphType::CVertexIterator, typename GraphType::CVertexIterator>& GetParents() const;

private:

    bool result;
    typedef map<typename GraphType::CVertexIterator, typename GraphType::EdgeType> WeightsType;
    map<typename GraphType::CVertexIterator, typename GraphType::EdgeType> minWeights;
    map<typename GraphType::CVertexIterator, typename GraphType::CVertexIterator> parents;
    GraphType& graph;
    const typename GraphType::CVertexIterator& firstVertex;
};

template <typename GraphType>
CFordBellman<GraphType>::CFordBellman(GraphType& _graph,
    const typename GraphType::CVertexIterator& _firstVertex)
: graph(_graph), firstVertex(_firstVertex)
{}

template <typename GraphType>
const map<typename GraphType::CVertexIterator, typename GraphType::EdgeType>&
CFordBellman<GraphType>::GetMinPathWeights() const
{
    return this->minWeights;
}

template <typename GraphType>
const map<typename GraphType::CVertexIterator, typename GraphType::CVertexIterator>&
CFordBellman<GraphType>::GetParents() const
{
    return this->parents;
}

template <typename GraphType>
void CFordBellman<GraphType>::Process()
{
    result = true;
    minWeights.clear();
    parents.clear();
    minWeights[firstVertex] = graph.GetEdgeTypeZeroValue();

    for (int i = 0; i < graph.GetVertexCount() && result; ++i)
    {
        result = false;

        for (typename GraphType::CEdgeIterator edgeIter = graph.GetEdgeListBegin();
                                      edgeIter != graph.GetEdgeListEnd(); ++edgeIter)
        {
            typename WeightsType::iterator fromVertex = minWeights.find(edgeIter.GetBeginVertex());

            if (fromVertex == minWeights.end())
            {
                continue;
            }

            typename GraphType::EdgeType newLength = fromVertex->second + *edgeIter;
            typename WeightsType::iterator toVertex = minWeights.find(edgeIter.GetEndVertex());

            if ((toVertex == minWeights.end()) || (toVertex->second > newLength))
            {
                minWeights[edgeIter.GetEndVertex()] = newLength;
                result = true;
                parents[edgeIter.GetEndVertex()] = edgeIter.GetBeginVertex();
            }
        }
    }
}

#endif // BELLMAN-FORD_H_INCLUDED
